package hard;

/**
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 *
 * 示例：
 *      输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 *      输出：6
 *      解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 */
public class leetcode53 {
    public static void main(String[] args) {
        System.out.println(maxSubArray(new int[]{5,4,-1,7,8}));
    }

    public static int maxSubArray(int[] nums) {
        // 动态规划：将问题划分为若干子问题，将子问题的解合并到大问题以解决复杂的大问题
        // 暴力算法容易导致很多值重复计算，影响效率

        // 定义一个用来存储所有子数组的最大和
        /*int[] dp = new int[nums.length]; // dp[i] 存储所有子数组的最大和
        // 将数组第一个元素定义为0 ~ 0的最大子数组和
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
        // 如果前一位的最大和大于零，则继续向后计算，存入dp[]
            if (dp[i - 1] > 0){
                dp[i] = dp[i - 1] + nums[i];
            } else {
            // 如果前一位的最大和小于0，则从当前数为最大子数组的第一位，继续计算
                dp[i] = nums[i];
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i : dp) {
            max = Math.max(i, max);
        }
        return max;*/

        // 最优解
        int pre = 0;
        int res = nums[0];
        for (int num : nums) {
            pre = Math.max(pre + num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
}
